package q41_firstMissingPositive;

public class Solution_2 {
    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[] {
            1,2,4,5,6
        }));
    }

    /**
     * 对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1, N+1] 中。这是因为如果 [1, N]都出现了，那么答案是 N+1，否则答案是 [1, N]中没有出现的最小正整数。
     * 这样一来，我们将所有在 [1,N] 范围内的数放入哈希表，也可以得到最终的答案。
     * 而给定的数组恰好长度为 N，这让我们有了一种将数组设计成哈希表的思路：
     * 我们对数组进行遍历，对于遍历到的数 x，如果它在 [1, N] 的范围内，那么就将数组中的第 x-1 个位置（注意：数组下标从 0 开始）打上「标记」。
     * 在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 N+1，否则答案是最小的没有打上标记的位置加 1。
     * 那么如何设计这个「标记」呢？由于数组中的数没有任何限制，因此这并不是一件容易的事情。但我们可以继续利用上面的提到的性质：由于我们只在意 [1, N] 中的数，
     * 因此我们可以先对数组进行遍历，把不在 [1, N] 范围内的数修改成任意一个大于 N 的数（例如 N+1）。这样一来，数组中的所有数就都是正数了，因此我们就可以将「标记」表示为「负号」。算法的流程如下：
     * 我们将数组中所有小于等于 0 的数修改为 N+1；
     * 我们遍历数组中的每一个数 x，它可能已经被打了标记，因此原本对应的数为 |x|，如果 |x| in [1, N]，那么我们给数组中的第 |x| - 1个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；
     * 在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 N+1，否则答案是第一个正数的 位置 加 1。
     */
    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        // 我们可以用1 2 4 5 6来检验，这里一共有n = 5 个数，那么数字x对应位置的都会被换成负数，唯独第三个位置没有被换
        // 所以到位置i = 2的时候，就得到了缺失的正数
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;

    }
}
